/* 
	Grupo 2

	Alunos: 
		Luis Felipe Souza de Mattos   RA: 107822
	
		Debora Maia Silva 	      RA: 101985
*/
/* Programa que dada uma imagem em escala de cinza no formato pgm, o numero de sementes e as posicoes das
sementes na figura, calcula usando o algoritmo LDA(linha divisora da aguas), que simula o preenchimento
homogeneo de etiquetas diferentes a partir de cada semente, tendo como prioridade os pontos mais baixos */

#include <stdio.h>
#include <stdlib.h>
#include "lda.h"

void lda(Imagem *img, Imagem **rotulo)
{
     ListaOrdenada *inicio;
     int comeco, n;
     
     comeco = 0;
     
     /* cria filas ordenadas para trabalhar nelas */
     inicio = (ListaOrdenada* )MontaListaOrdenada();
     
     /* inserindo nas filas o pixels basicos que jah foram etiquetados */
     IniciaFila(img, *rotulo, inicio, comeco);
     
     /* numero total de elementos da matriz para controlar qnd for percorrer */
     n = img->nlins * img->ncols;
     
     Inunda(*rotulo, inicio, n, img, 0);

	/* libera a memoria usada pelo que restou da fila ordenada */
	LiberaListaOrdenada(inicio);
	       
     return;
     
}

/* funcao recursiva que inunda a partir da maior prioridade */
void Inunda(Imagem *rotulo, ListaSimples **inicio, int total,Imagem *img, int linhavet)
{
     int linha, coluna, posicao, prioridade,n,etq,indice;
	ListaSimples *atual;
  
	n = rotulo->ncols * rotulo->nlins;
     
     if(linhavet < 256)
     {
	  	/* estando etiquetada, retira da fila e inunda seus vizinhos */
		if (inicio[linhavet]->prox == NULL)
		{
			LiberaListaSimples(&inicio[linhavet]);
			Inunda(rotulo, inicio, total, img, linhavet + 1);
		}
	  	else
	  	{
			/* retira o elemento que chegou primeiro de maior prioridade */
	       	atual = TiraElemento(inicio);
			/* guarda o valor da etiqueta e o indice do elemento */
			etq = rotulo->val[atual->indice];
			indice = atual->indice;

			/* calcula a linha e a coluna do pixel a partir do indice */
			if (indice == 0)
			{
				linha = 0;
				coluna = 0;
			}
			else
			{
				linha = (indice)/(img->ncols);
				coluna = (indice)%(img->ncols);
			}
	       
			/* inundar os vizinhos inserindo-os na lista ordenada */
			  
			/* inserindo vizinho 1, caso o elemento atual nao esteja na primeira linha */
			if (linha != 0)
			{
			  	posicao = rotulo->lin[linha - 1] + coluna;
			  	prioridade = (img)->val[posicao];
				if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			}
			/* inserindo vizinho 2, caso o elemento atual nao esteja na primeira linha ou na ultima coluna */
			if (linha != 0 && coluna != img->ncols - 1)
			{
				posicao = rotulo->lin[linha - 1] + (coluna + 1);
			  	prioridade = (img)->val[posicao];
			 	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 3, caso o elemento atual nao esteja na ultima coluna */
			if (coluna != img->ncols - 1)
			{
				posicao = rotulo->lin[linha] + (coluna + 1);
			  	prioridade = (img)->val[posicao];
			 	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 4, caso o elemento atual nao esteja na ultima linha ou na ultima coluna */
			if (linha != img->nlins - 1 && coluna != img->ncols - 1)
			{
				posicao = rotulo->lin[linha + 1] + (coluna + 1);
			  	prioridade = (img)->val[posicao];
			  	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 5, caso o elemento atual nao esteja na ultima linha */
			if (linha != img->nlins - 1)
			{
				posicao = rotulo->lin[linha + 1] + (coluna);
			  	prioridade = (img)->val[posicao];
			  	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
					InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 6, caso o elemento atual nao esteja na ultima linha ou na primeira coluna*/
			if (linha != img->nlins - 1 && coluna != 0)
			{
				posicao = rotulo->lin[linha + 1] + (coluna - 1);
			  	prioridade = (img)->val[posicao];
			  	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 7, caso o elemento atual nao esteja na primeira coluna */
			if (coluna != 0)
			{
				posicao = rotulo->lin[linha] + (coluna - 1);
			  	prioridade = (img)->val[posicao];
			  	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			} 
			/* inserindo vizinho 8, caso o elemento atual nao esteja na primeira linha ou na primeira coluna */
			if (linha != 0 && coluna != 0)
			{
				posicao = rotulo->lin[linha - 1] + (coluna - 1);
			 	 prioridade = (img)->val[posicao];
			  	if (rotulo->val[posicao] == 0)
				{
					rotulo->val[posicao] = etq;
				  	InsereListaOrdenada(inicio,prioridade,posicao, img);
				}
			}
	       	
			/* libera a memoria usada pelo elemento atual */
	       	LiberaElemento(atual);

			/* chama a funcao novamente para a mesma prioridade */
			Inunda(rotulo, inicio, total, img, linhavet);
	  	}
     }
}
